package  
{
	import flash.display.*;
	import flash.events.*;
	import flash.utils.*;
	
	/**
	 * 快速排序测试
	 * @author StefanieKaka
	 */
	public final class QuickSortTest extends Sprite 
	{
		
		public function QuickSortTest() 
		{
			this.stage.addEventListener(MouseEvent.CLICK, onMouseClickHandler);
		}
		
		private function onMouseClickHandler(evt : MouseEvent) : void
		{
			var startTime : int = getTimer();
			for (var k : int = 0; k < 1; ++k)
			{
				m_numbers = new Vector.<int>();
				for (var i : int = 0; i < 1000; ++i)
					m_numbers.push(int(Math.random() * 100));
				quickSort(m_numbers, 0, m_numbers.length - 1);
				
				//trace(m_numbers);
			}
			trace(getTimer() - startTime);
		}
		
		/// 分割
		private function partition(numbers : Vector.<int>, low : int, high : int) : int
		{
			var pivotkey : int = numbers[low];
			while (low < high)
			{
				while (low < high && numbers[high] >= pivotkey)
					--high;
				numbers[low] = numbers[high];
				
				while (low < high && numbers[low] <= pivotkey)
					++low;
				numbers[high] = numbers[low];
			}
			
			numbers[low] = pivotkey;
			return low;
		}
		
		/// 排序
		private function quickSort(numbers : Vector.<int>, low : int, high : int) : void
		{
			if (low < high)
			{
				var pivotloc : int = partition(numbers, low, high);
				quickSort(numbers, low, pivotloc - 1);
				quickSort(numbers, pivotloc + 1, high);
			}
		}
		
		private var m_numbers : Vector.<int> = null;
		
	}

}